package com.codingvip.backtracking;

public class Pattern {
    private boolean matched = false;
    private char[] pattern;
    private int patterlen; //正则表达室长度

    public Pattern(char[] pattern, int patterlen) {
        this.pattern = pattern;
        this.patterlen = patterlen;
    }

    public boolean match(char[] text, int tlen) {
        matched = false;
        rmatch(0, 0, text, tlen);
        return matched;
    }

    /**
     * @param ti
     * @param pj
     * @param text
     * @param tlen
     */
    private void rmatch(int ti, int pj, char[] text, int tlen) {
        if (matched) {
            return;
        }
        if (pj == patterlen) {
            if (ti == tlen) {
                matched = true;
            }
            return;
        }
        if (pattern[pj] == '*') {
            //匹配任意个字符
            for (int k = 0; k <= tlen - ti; ++k) {
                rmatch(ti + k, pj + 1, text, tlen);
            }
        } else if (pattern[pj] == '?') {
            rmatch(ti, pj + 1, text, tlen);
            rmatch(ti + 1, pj + 1, text, tlen);
        } else if (ti < tlen && pattern[pj] == text[ti]) {
            rmatch(ti + 1, pj + 1, text, tlen);
        }

    }
}
